# 三数之和：https://leetcode-cn.com/problems/3sum/submissions/ 
# 视频讲解该系列问题： https://www.bilibili.com/video/BV1af4y1W7e2?p=18&spm_id_from=pageDriver
# 方法一
class Solution:
    def threeSum(self, nums: List[int]):
        """ 三层循环暴力破解 加上排序去重 """
        n = len(nums)
        rst = set()
        nums.sort()
        for i in range(n):
            for j in range(i+1, n):
                for k in range(j+1, n):
                    # 进行判断
                    if nums[i] + nums[j] + nums[k] == 0:  
                        rst.add((nums[i], nums[j], nums[k]))
        return list(rst)

    
# 方法二
class Solution:
    def threeSum(self, nums: List[int]):
        """ 一层循环加上 双指针解题： 紧跟 两数之和双指针解题！思路贯通 """
        n = len(nums)
        rst = set()
        nums.sort()
        for i in range(n):
            low, high = i+1, n-1
            while low < high:
                if nums[low] + nums[high] + nums[i] == 0:
                    rst.add((nums[i], nums[low], nums[high]))
                    # low += 1 或者 high -= 1 继续查找，不能够break结束查找，可能漏掉一些结果
                    low += 1
                elif nums[low] + nums[high] + nums[i] < 0:
                    low += 1
                else:
                    high -= 1 
        
        return list(rst)


# 接着进行进一步优化 
class Solution:
    def threeSum(self, nums: List[int]):
        """ 一层循环加上 双指针解题： 紧跟 两数之和双指针解题！思路贯通 """
        n = len(nums)
        rst = list()
        nums.sort()
        for i in range(n):
            low, high = i+1, n-1
            # 优化： 大于0 就不能再 和为 0
            if nums[i] > 0:
                break
            # 优化： i 代表的值，也不能重复，否则也会取到重复的元素
            if i > 0 and nums[i] == nums[i-1]:
                continue

            while low < high:
                if nums[low] + nums[high] + nums[i] == 0:
                    rst.append([nums[i], nums[low], nums[high]])
                    # 优化： 去除重复值，不使用set去重，优化效率, 这是针对第二个和第三个进行的。第一个数如果重复，还是会导致结果集重复，所以 要对 i 也进行去重
                    x, y = nums[low], nums[high]
                    while nums[low] == x and low < high:
                        low += 1
                    while nums[high] == y and low < high:
                        high -= 1

                elif nums[low] + nums[high] + nums[i] < 0:
                    low += 1
                else:
                    high -= 1 
        
        return rst
